1. 题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1: 输入: "()" 输出: true

示例 2: 输入: "()[]{}" 输出: true

示例 3: 输入: "(]" 输出: false

示例 4: 输入: "([)]" 输出: false

示例 5: 输入: "{[]}" 输出: true

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

栈的简单应用。括号匹配。

官方题解中用哈希表中的一个键值对存储一对匹配的括号。挺好的表示方法。能减少后续一定量的代码量。

unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
};

3. 代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> tmp;
        for(auto ch:s){
            if(!tmp.empty()){
                switch (ch){
                    case ')':
                        if(tmp.top()=='(') tmp.pop();
                        else return false;
                        break;
                    case ']':
                        if(tmp.top()=='[') tmp.pop();
                        else return false;
                        break;
                    case '}':
                        if(tmp.top()=='{') tmp.pop();
                        else return false;
                        break;
                    default:
                        tmp.push(ch);
                        break;
                }  
            }
            else tmp.push(ch);
        }
        if(tmp.empty()) return true;
        else return false;
    }
};

看到了一种比较巧妙的写法：

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == '[') stack.push(']');
            else if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || c != stack.pop()) return false;
        }
        return stack.isEmpty();
    }
}